package sort;

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

public class TestSort {
    /**
     * 插入排序(从小到大) 对数据敏感
     * 【直接插入排序的使用场景是：当数据量小，并且已经趋于有序的时候，使用直接插入排序】
     * 时间复杂度：最坏情况下（逆序）：O(n^2)
     * 最好情况下（本来就是升序）：O(n)
     * 空间复杂度：O(1)
     * 稳定性：是稳定的
     * 如果本身就是一个稳定的排序，我们可以实现为不稳定的，但是如果本身就是不稳定的排序，那么就不可能变成一个稳定的排序。
     * @param array
     */
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length ; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >=0 ; j--) {
                if(array[j]>tmp){
                    array[j+1]=array[j];

                }else {
                   // array[j+1]=tmp;
                    break;
                }

            }
            array[j+1]=tmp;
            
        }

    }
    public static void shell(int[] array,int gap){
        for (int i = gap; i < array.length ; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >=0 ; j-=gap) {
                if(array[j]>tmp){
                    array[j+gap]=array[j];

                }else {
                    // array[j+1]=tmp;
                    break;
                }

            }
            array[j+gap]=tmp;

        }


    }
    /**
     * 希尔排序：缩小增量的排序（是对直接插入排序的优化）
     * 时间复杂度：O(n^1.3)或O*(n^1.5)//科学家还没研究明白
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void shellSort(int[] array){
        int gap = array.length;
        while (gap>1){
            shell(array,gap);
            gap/=2;

        }
        shell(array,1);

    }

   
    /**
     *选择排序
     * 时间复杂度：O(n^2)//不管有序无序
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;
            for (int j = i+1; j < array.length ; j++) {
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
                
            }
                swap(array,i,minIndex);

            
        }

    }
    private static void shiftDown(int[] array, int root, int len){
        int parent=root;
        int child=2*parent+1;
        while (child<len){
            if(child+1<len&&array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }

    }
    private static void createHeap(int[] array){
        for (int p = (array.length-1-1)/2; p >=0; p--) {
            shiftDown(array,p, array.length);
            
        }
    }

    /**
     * 堆排序
     * 时间复杂度：O(n*logn)【不管有序无序】
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void heapSort(int[] array){
        createHeap(array);
        int end=array.length-1;
        while (end>=0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }

    }

    /**
     * 冒泡排序
     * 时间复杂度：O(n^2)
     * 稳定性：稳定
     * @param array
     */
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                }
                
            }
            
        }
    }

    /**
     * 冒泡排序优化版
     * @param array
     */
    public static void bubbleSort2(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flg=false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }

            }
            if(flg==false){
                break;
            }

        }
    }
    private static void swap(int[] array,int i,int j){
        int tmp= array[i];
        array[i]=array[j];
        array[j]=tmp;

    }

    /**
     * Hoare版找到基准值
     * 左边做key,右边先走
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int partitionHoare(int[] array,int low,int high){
        int i=low;
        int tmp=array[low];
        while (low<high){
            while (low<high&&array[high]>=tmp){//不加等号且左右都为tmp值可能会导致死循环
                high--;
            }
            //此时high下标就是你要找的数字
            while (low<high&&array[low]<=tmp){
                low++;
            }
            //此时low下标就是你要找的数字
            swap(array,low,high);
        }
        swap(array,low,i);
        return low;

    }

    /**
     * 挖坑法求基准值,与其他方法相比较为重要
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int partitionHole(int[] array,int low,int high){
        int tmp = array[low];
        while (low<high){
            while (low<high&&array[high]>=tmp){
                high--;
            }
            array[low]=array[high];
            while (low<high&&array[low]<=tmp){
                low++;
            }
            array[high]=array[low];
        }
        array[low]=tmp;
        return low;

    }

    /**
     * 前后（双）指针法写法1__推荐理解用
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] array,int left,int right){
        int d = left + 1;
        int pivot = array[left];
        for (int i = left + 1; i <= right; i++) {
            if (array[i] < pivot) {
                swap(array, i, d);
                d++;
            }
        }
        swap(array, d - 1, left);
        return d - 1;


    }

    /**
     * 前后指针法写法2
     * @param array
     * @param low
     * @param high
     */
    private static int partition2(int[] array,int low,int high){
        int prev=low;
        int cur=low+1;
        while (cur<=high){
            if(array[cur]<array[low]&&array[++prev]!=array[cur]){
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,low);
        return prev;


    }

    /**
     * 范围内的插入排序
     * @param array
     * @param low
     * @param end
     */
    public static void insertSortRange(int[] array,int low,int end){
        for (int i = low+1; i <=end ; i++) {
            int tmp=array[i];
            int j=i-1;
            for (; j>=low; j--) {
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else {
                    break;
                }

            }
            array[j+1]=tmp;
            
        }

    }

    /**
     * 递归快排
     * @param array
     * @param left
     * @param right
     */
    private static void quick(int[] array,int left,int right){
        if(left>=right) return;
        int pivot=partition(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);

    }

    /**
     * 非递归快排
     * @param array
     */
    public static void quickNor(int[] array){
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        int pivot=partition(array,left,right);//找基准的时候排序，栈是实现递归的部分了
        //左边有两个以上数据
        if(pivot>left+1){
            stack.push(left);
            stack.push(pivot-1);

        }
        //右边有两个以上数据
        if(pivot<right-1){
            stack.push(pivot+1);
            stack.push(right);

        }
        while (!stack.empty()){
            right=stack.pop();
            left=stack.pop();
            pivot=partition(array,left,right);
            //左边有两个以上数据
            if(pivot>left+1){
                stack.push(left);
                stack.push(pivot-1);

            }
            //右边有两个以上数据
            if(pivot<right-1){
                stack.push(pivot+1);
                stack.push(right);

            }
        }

    }

    /**
     * 找到三个数字中间大小的数字的下标
     * 目的是为了降低树的高度
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int medianOfThreeIndex(int[] array,int left,int right){
        //+优先级大于>>>所以后面要加()
        int mid=left+((right-left)>>>1);
        //或者写成int mid=(low+high)/2;
        if(array[left]<array[right]){
            if(array[mid]<array[left]){
                return left;
            }else if(array[mid]>array[right]){
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid]<array[right]){
                return right;
            } else if (array[mid]>array[left]) {
                return left;
            }else {
                return mid;
            }
        }

    }

    /**
     * 对quick进行优化（利用插入排序）
     * 并没有根本上解决递归深度太深的情况
     * [left,right]
     * @param array
     * @param left
     * @param right
     */
    private static void quick1(int[] array,int left,int right){
        if(left>=right) return;
        //1.在某个区间的时候，使用直接插入排序【优化的区间内的比较】
        if(right-left+1<=15){
            //进行插入排序
            insertSortRange(array,left,right);
            return;
        }
        //2.三数取中法【优化的是本身的分割从而减少递归的深度】（真正意义上的优化）
        int index=medianOfThreeIndex(array,left,right);
        swap(array,left,index);
        //3.将基准相同的数字靠到一起从而减少递归的区间
        //https://blog.csdn.net/hgzhgzhgz/article/details/58064221?utm_source=itdada0&utm_medium=referral
        int pivot=partition(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);

    }

    /**
     * 快排quick
     * 时间复杂度：
     * 好的情况下：O(n*logn) 数据有序或者逆序：O(n^2)
     * 空间复杂度：
     * 好的情况下：O(logn) 最坏情况下：O(n)
     * 稳定性：不稳定
     * 这是未优化版本，数据太多可能会导致栈溢出
     * @param array
     */
    public static void quickSort(int[] array){
        quick(array,0, array.length-1);

    }
    private static void merge(int[] array,int low,int mid,int high){
        int s1=low;
        int e1=mid;
        int s2=mid+1;
        int e2=high;
        int[] tmpArr=new int[high-low+1];
        int k=0;//代表tmpArr的下标
        while (s1<=e1&&s2<=e2){//证明两个段都有数据
            if(array[s1]<=array[s2]){
                tmpArr[k++]=array[s1++];
            }else {
                tmpArr[k++]=array[s2++];
            }
        }
        //可能剩下多个，剩余元素全部挪过来
        while (s1<=e1){
            tmpArr[k++]=array[s1++];
        }
        while (s2<=e2){
            tmpArr[k++]=array[s2++];
        }
        for (int i = 0; i <k ; i++) {
                array[i+low]=tmpArr[i];
            }
    }
    private static void mergeSortInternal(int[] array,int low,int high){
        if(low>=high) return;
        int mid=low+((high-low)>>>1);
        //或者写成int mid=(low+high)/2;
        mergeSortInternal(array,low,mid);
        mergeSortInternal(array,mid+1,high);
        merge(array,low,mid,high);

    }

    /**
     * 归并排序
     * 时间复杂度：O(n*logn)【和数据是否有序没有关系】
     * 空间复杂度：O(n)
     * 稳定性：稳定
     * 插入 冒泡 归并 都稳定
     * @param array
     */
    public static void mergeSort(int[] array){
        mergeSortInternal(array,0,array.length-1);

    }

    /**
     * 非递归的归并排序
     * @param array
     */
    public static void mergeSortNor(int[] array){
        int gap=1;
        while (gap<array.length){
            for (int i = 0; i < array.length; i+=2*gap) {
                int left=i;
                int mid=left+gap-1;
                //修正mid
                if(mid>=array.length){
                    mid=array.length-1;
                }
                //修正right
                int right=mid+gap;
                if(right>=array.length){
                    right=array.length-1;
                }
                merge(array,left,mid,right);
                
            }
            gap*=2;
        }

    }

    /**
     * 计数排序
     * 时间复杂度:O(范围+n)
     * 空间复杂度:O(范围)
     * 计数排序和当前数据给定的范围是有关系的
     * int range=maxVal-minVal+1;
     * 集中的好点：0-100->10
     * 稳定性：此代码不一定稳定
     * 但是课件上用了B数组的代码是稳定的
     * @param array
     */
    public static void countSort(int[] array){
        int maxVal=array[0];
        int minVal=array[0];
        //1.获取到了最大值和最小值
        //O(n)
        for (int i = 1; i < array.length; i++) {
            if(array[i]<minVal){
                minVal=array[i];
            }
            if(array[i]>maxVal){
                maxVal=array[i];
            }
            
        }
        //2.开始计数
        int range=maxVal-minVal+1;
        int[] count=new int[range];
        //O(n)
        for (int i = 0; i <array.length ; i++) {
            count[array[i]-minVal]++;
        }
        int index=0;
        //3.遍历这个计数数组，把数据放回array
        //O(范围+n)
        for (int i = 0; i < count.length; i++) {
            while (count[i]>0){
                array[index++]=i+minVal;
                count[i]--;

            }
            
        }


    }

    public static void main(String[] args) {
        //int[] array={1};
        int[] array={6,1,6,3,4,2,10,9,36,45,8,19};
        System.out.println("排序前："+ Arrays.toString(array));
        countSort(array);
        System.out.println("排序后："+ Arrays.toString(array));

    }


    public static void main7(String[] args) {
        int[] array={6,1,6,3,4,2,10,9,36,45,8,19};
        System.out.println("排序前："+ Arrays.toString(array));
        mergeSortNor(array);
        System.out.println("排序后："+ Arrays.toString(array));

    }

    public static void main6(String[] args) {
        int[] array={6,1,6,3,4,2,10,9,36,45,8,19};
        System.out.println("排序前："+ Arrays.toString(array));
        //quickSort(array);
        quickNor(array);
        System.out.println("排序后："+ Arrays.toString(array));

    }
    public static void main5(String[] args) {
        int[] array={5,10,3,8,2};
        System.out.println("排序前："+ Arrays.toString(array));
        bubbleSort2(array);
        System.out.println("排序后："+ Arrays.toString(array));

    }

    public static void main4(String[] args) {
        int[] array={5,10,3,8,2};
        System.out.println("排序前："+ Arrays.toString(array));
        heapSort(array);
        System.out.println("排序后："+ Arrays.toString(array));

    }

    public static void main3(String[] args) {
        int[] array={5,10,3,8,2};
        System.out.println("排序前："+ Arrays.toString(array));
        selectSort(array);
        System.out.println("排序后："+ Arrays.toString(array));

    }

    public static void main2(String[] args) {
        //看时间的时候分开测，不然同时测，就是排完序的又排一遍
        int[] array=new int[10_0000];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i]=100000-i;
            //array[i]=random.nextInt(10_000);
            
        }
        long startTime=System.currentTimeMillis();
        //shellSort(array);
        long endTime=System.currentTimeMillis();
        System.out.println("希尔排序："+(endTime-startTime));

        startTime=System.currentTimeMillis();
        insertSort(array);
        endTime=System.currentTimeMillis();
        System.out.println("插入排序："+(endTime-startTime));
    }

    public static void main1(String[] args) {
        int[] array={5,10,3,8,2};
        System.out.println("排序前："+ Arrays.toString(array));
        insertSort(array);
        System.out.println("排序后："+ Arrays.toString(array));

    }
}
